// https://leetcode.cn/problems/design-add-and-search-words-data-structure/
// Created by ade on 2022/9/5.
// 请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
//
//实现词典类 WordDictionary ：
//
//WordDictionary() 初始化词典对象
//void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
//bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
//
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>


using namespace std;

struct Trie {
    bool isEnd;
    vector<Trie *> children;

    Trie() : children(26), isEnd(false) {}
};


class WordDictionary {
public:
    unordered_map<int, unordered_map<int, Trie *>> m = {};

    WordDictionary() {}

    void addWord(string word) {
        Trie *node = nullptr;
        int len = word.size();
//        if (m.find(len) == m.end()) {
//            m.insert({len, {}});
//        }
        if (m.find(len) == m.end()) m[len] = {};
        int start = word[0] - 'a';
        // 注意：嵌套map访问内层数据的时候，务必直接访问，否则会有意想不到的错误
        node = m[len][start];
        if (!node) {
            m[len][start] = new Trie();
            node = m[len][start];
        }
        for (auto i : word) {
            if (!node->children[i - 'a'])
                node->children[i - 'a'] = new Trie();
            node = node->children[i - 'a'];
        }
        node->isEnd = true;
    }

    bool search(string t) {
        int len = t.size();
        if (m.find(len) == m.end()) {
            return false;
        }
        if (t[0] == '.') {
            for (auto i : m[len]) {
                if (searchNode(i.second, t, 0)) return true;
            }
        } else {
            return searchNode(m[len][t[0] - 'a'], t, 0);
        }
        return false;
    }

    bool searchNode(Trie *node, string &word, int index) {
        if (!node) {
            return false;
        }
        if (index == word.size()) {
            return node->isEnd;
        }

        if (word[index] == '.') {
            for (int i = 0; i < 26; i++) {
                if (node->children[i] && searchNode(node->children[i], word, index + 1)) return true;
            }
        } else {
            return node->children[word[index] - 'a'] && searchNode(node->children[word[index] - 'a'], word, index + 1);
        }

        return false;
    }
};


int main() {
//    ["WordDictionary","addWord","addWord","addWord","addWord","search","search","addWord","search","search","search","search","search","search"]
//    [[],["at"],["and"],["an"],["add"],   ["a"],[".at"],  ["bat"],   [".at"],["an."],  ["a.d."],["b."],["a.d"],["."]]
//    [null,null,null,null,null,false,false,null,true,false,false,false,true,false]
//    [null,null,null,null,null,false,false,null,true,true, false,false,true,false] xgvk"],["wykzbvwdsoyfowqicymzd"],["xajbtjyjuwgoynjgu
    WordDictionary w;
    w.addWord("xgvk");
    w.addWord("wykzbvwdsoyfowqicymzd");
    //         wykzbvwdso..owqicymzd
    w.addWord("xajbtjyjuwgoynjgu");

//    cout << w.search("a") << endl;
//    cout << w.search(".at") << endl;

//    w.addWord("bat");

//    cout << w.search(".at") << endl;
    cout << w.search("wykzbvwdso..owqicymzd") << endl;
    return 0;
}